package day1;

import java.util.Arrays;

/**
 * 插入排序算法实现
 * 主要思路：
 * 当前0～0位置有序
 * 0～i位置比较满足有序。也就是i与i-1比较是否有序
 */
public class InsertionSort {


    public static void insertionSort(int[] array){
        if (array==null||array.length<2) {
            return ;
        }

        //0~0有序
        //0～i有序
        for (int i = 1; i < array.length; i++) {
            //做到0～i范围有序

            //当前数往左换，换到数组最开始或者满足条件
            for (int j = i-1; j>=0&&array[j]>array[j+1]; j--) {
                    swap(array,j,j+1);
            }
        }
    }

    private static void swap(int[] array, int i, int j) {
       array[i]=array[i]^array[j];
       array[j]=array[i]^array[j];
       array[i]=array[i]^array[j];
    }

    /*======================对数器的实现============================= */ 

    public static void main(String[] args) {
        int testTime =500000; //测试次数
        int maxSize=100; //数组最大长度
        int maxValue=100; //数组最大值
        boolean succeed=true;

        for (int i = 0; i < testTime; i++) {
            int[] array1=generateRadomArray(maxSize,maxValue);
            int[] array2=copyArray(array1);
            insertionSort(array1);
            comparator(array2);
            if (!isEqual(array1,array2)) {
                succeed=false;
                break;
            }
        }
        System.out.println(succeed?"Nice!":"Very bad!");

        int[] array=generateRadomArray(maxSize,maxValue);
        printArray(array);
        insertionSort(array);
        printArray(array);
    }

    private static void printArray(int[] array) {
        System.out.println("[ ");
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]+" ");
        }
        System.out.print("]");
        System.out.println(" ");
    }

    private static boolean isEqual(int[] array1, int[] array) {
        for (int i = 0; i < array.length; i++) {
            if (!(array1[i]==array[i])) {
                return false;
            }
        }
        return true;
    }

    //jdk提供的已知正确方法，用于对比需要测试的算法
    private static void comparator(int[] array) {
        Arrays.sort(array);
    }

    /**
     * 复制数组
     * @param array 愿数组
     * @return 复制的新数组
     */
    private static int[] copyArray(int[] array) {
        if (array==null) {
            return null;
        }

        int[] res=new int[array.length];
        for (int i = 0; i < array.length; i++) {
            res[i]=array[i];
        }
        return res;
    }

    /**
     * 生成随机长度、包含随机值的数组
     * @param maxSize 数组最大长度
     * @param maxValue 数组中的值最大值
     * @return 生成的数组
     */
    private static int[] generateRadomArray(int maxSize, int maxValue) {
        
        /**
         * 
         * Math.random()->[0,1)所有小数，等概率返回。
         * 因为计算机有精度因此可以穷尽，数学则无法做到
         * 
         * Math.random()*N->[0,N)所有小数，等概率返回。
         * 
         * (int)(Math.random()*N)->[0,N-1]所有整数，等概率返回
         * 
         */
        
         //生成随机长度的数组
         int[] array=new int[(int) ((maxSize+1)*Math.random())];

         //使用随机数初始化数组
         for (int i = 0; i < array.length; i++) {
            array[i]=(int) ((maxValue+1)*Math.random())-(int)((maxValue)*Math.random());
         }

        return array;
    }
}
